package _interview75;

import _object.TreeNode;

/**
 * 1372. 二叉树中的最长交错路径
 */
public class No1372 {
    private int ans = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return ans - 1;
    }

    private void dfs(TreeNode node, boolean goRight, int curDeep) {
        if (node == null) return;
        ans = Math.max(ans, curDeep + 1);
        if (goRight) {
            // 继续走
            dfs(node.right, false, curDeep + 1);
            // 重头开始走
            dfs(node.left, true, 1);
        } else {
            // 继续走
            dfs(node.left, true, curDeep + 1);
            // 重头开始走
            dfs(node.right, false, 1);
        }
    }
}
